package algorithm.linkedList;

/**
 * 划分链表，我们准备小头小尾，大头大尾四个链表指针
 * 类似分治的思想，先分开处理，最后再合并。合并的操作比较简单，用指针相连即可
 */
public class PartitionList {
    public static ListNode partitionList(ListNode head,int target){
        ListNode leftHead=null,leftTail=null;
        ListNode rightHead=null,rightTail=null;
        ListNode next=null;
        while(head!=null){
            //借助next记录head.next，防止地址丢失
            next=head.next;
            head.next=null;
            if(head.val<target){
                //这时应当挂在左边区域
                if(leftHead==null){
                    leftHead=head;
                }else{
                    //说明左边已经有元素了，需要挂在小尾的后面
                    leftTail.next=head;
                }
                leftTail=head;
            }else{
                if(rightHead==null){
                    rightHead=head;
                }else{
                    rightTail.next=head;
                }
                rightTail=head;
            }
            head=next;
        }
        if(leftHead==null) return rightHead;
        leftTail.next=rightHead;
        return leftHead;
    }
}
